package CorporateInterview;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author ChanZany
 * @Date 2021/5/19 11:21
 * @Version 1.0
 * 3
 * 1 2
 * 2 3
 * 3 4
 * 此时最大队伍成员数量为4，因为1跟随了2,2又跟随了3,3又跟随了4，队伍成员是[1,2,3,4]。
 */
public class ZJ3 {

    static int[] a; //a[i]=k 表示i的父节点是k
    static int max = Integer.MIN_VALUE;
    static Map<Integer,Integer> map = new HashMap<>();
    public static void main(String[] args) {
        int n =3;
        int x1=1,y1=3;
        int x2=2,y2=3;
        int x3=4,y3=4;
        a = new int[n*2];
        int[] input = {x1,x2,x3,y1,y2,y3};
        init(input);
        union(x3,y3);
        union(x2,y2);
        union(x1,y1);
        for(int value:map.values()){
            max = Math.max(value+1,max);
        }
        System.out.println(max);
    }

    private static void union(int i, int j) {
        int fa_i = find(i);
        int fa_j = find(j);
        a[fa_i] = fa_j; //i的祖先指向j的祖先
        if (map.containsKey(fa_j)) { //记录fa_j被作为祖先的次数
            map.put(fa_j, map.get(fa_j) + 1);
        } else {
            map.put(fa_j, 1);
        }
    }

    private static int find(int x){
        if (a[x]==x) return x;
        a[x] = find(a[x]); //父节点设为根节点
        return a[x];
    }

    private static void init(int [] input) {
        for (int i=0;i<input.length;i++){
            a[input[i]] = input[i];
        }
    }
}
